#include <algorithm>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
#include<cstring>
using std::swap;
using std::sort;
using std::cin;
using std::cout;
using std::endl;

typedef long long LL;
const int TIME = 11;
LL factor[1000000];
int fac_top;
LL abs(LL n)
{
	if (n < 0)
		return -n;
	return n;
}
LL gcd(LL small, LL big)
{
	while (small)
	{
		swap(small, big);
		small %= big;
	}
	return abs(big);
}
//ret = (a*b)%n (n<2^62)
LL muti_mod(LL a, LL b, LL n)
{
	LL exp = a % n, res = 0;
	while (b)
	{
		if (b & 1)
		{
			res += exp;
			if (res > n)
				res -= n;
		}
		exp <<= 1;
		if (exp > n)
			exp -= n;
		b >>= 1;
	}
	return res;
}
// ret = (a^b)%n
LL mod_exp(LL a, LL p, LL m)
{
	LL exp = a % m, res = 1; //
	while (p > 1)
	{
		if (p & 1) //
			res = muti_mod(res, exp, m);
		exp = muti_mod(exp, exp, m);
		p >>= 1;
	}
	return muti_mod(res, exp, m);
}
bool miller_rabin(LL n, int times)
{
	if (n == 2)
		return 1;
	if (n < 2 || !(n & 1))
		return 0;
	LL a, u = n - 1, x, y;
	int t = 0;
	while (u % 2 == 0)
	{
		t++;
		u /= 2;
	}
	srand(time(0));
	for (int i = 0; i < times; i++)
	{
		a = rand() % (n - 1) + 1;
		x = mod_exp(a, u, n);
		for (int j = 0; j < t; j++)
		{
			y = muti_mod(x, x, n);
			if (y == 1 && x != 1 && x != n - 1)
				return false; //must not
			x = y;
		}
		if (y != 1)
			return false;
	}
	return true;
}
LL pollard_rho(LL n, int c)
{
	LL x, y, d, i = 1, k = 2;
	srand(time(0));
	x = rand() % (n - 1) + 1;
	y = x;
	while (true)
	{
		i++;
		x = (muti_mod(x, x, n) + c) % n;
		d = gcd(y - x, n);
		if (1 < d && d < n)
			return d;
		if (y == x)
			return n;
		if (i == k)
		{
			y = x;
			k <<= 1;
		}
	}
}
void findFactor(LL n, int k)
{
	if (n == 1)
		return;
	if (miller_rabin(n, TIME))
	{
		factor[++fac_top] = n;
		return;
	}
	LL p = n;
	while (p >= n)
		p = pollard_rho(p, k--);
	findFactor(p, k);
	findFactor(n / p, k);
}

int main()
{
	int T;
	cin>>T;
	while(T--){
	memset(factor,0,sizeof(factor));
	fac_top = 0;
	LL K;
	cin>>K;
	if (K != 1)
		findFactor(K, 107);
	sort(factor + 1, factor + 1 + fac_top);
	int c = fac_top;
	fac_top = 0;
	for (int i = 1; i <= c;)
	{
		LL current = factor[i];
		factor[++fac_top] = current;
		for (; i <= c && current == factor[i]; i++)
			;
	}
	if(fac_top==1&&factor[1]==K)cout<<"Prime"<<endl;
	else cout<<factor[1]<<endl;
	}
	return 0;
}
